#include<iostream>
#include<cstdlib>

using namespace std;

typedef struct node Node;

struct node{
	int data;
	Node *next;
};

int LLInsert(Node **, int);
int LLDelete(Node **, int);
int LLSize(Node *);
int isLLEmpty(Node *);

void revPrintList(Node *);

int debug(Node *);

int main(){
	Node *head = NULL;
	for(int i=1; i<=5; i++){
		if(LLInsert(&head, i)){
			cout << "\nEntered " << i << " into the list";
		}else{
			cout << "\nInsert failed on " << i;
		}
	}
	
	debug(head);
	
	for(int i=1; i<=5; i+=2){
		if(int data = LLDelete(&head, i)){
			cout << "\nValue received from the list: " << data;
		}else{
			cout << "\nValue fetching failed! Is the List empty: " << (isLLEmpty(head)?"True":"False");
		}
	}
	
	debug(head);
	
	for(int i=6;i<=10;i++){
		if(LLInsert(&head, i)){
			cout << "\nEntered " << i << " into the list";
		}else{
			cout << "\nInsert failed on " << i;
		}
	}
	
	revPrintList(head);
	
	debug(head);
	cout << "\n--Linked List printed in reverse--\n";
	return 0;
}

int LLInsert(Node **head, int data){
	//This function will put the newNode at the head of the Linked List
	Node *newNode = new Node;
	newNode->data = data;
	if(*head){
		newNode->next = *head;
	}else{
		newNode->next = NULL;
	}
	*head = newNode;
	return 1;
}

int LLDelete(Node **head, int data){
	//Find and delete a given node
	Node *thisNode = *head, *previousNode = NULL;
	while(thisNode && thisNode->data != data){
		previousNode = thisNode;
		thisNode = thisNode->next;
	}
	data = thisNode->data;
	if(!previousNode){ //which means the head is to be deleted
		*head = thisNode->next;
	}else{
		previousNode->next = thisNode->next;
	}
	delete thisNode;
	return data;
}

int LLSize(Node *head){
	//traverse list and keep counters
	int count=0;
	Node *thisNode = head;
	while(thisNode){
		thisNode = thisNode->next;
		count++;
	}
	return count;
}

int isLLEmpty(Node *head){
	return (head == NULL);
}

void revPrintList(Node *head){
	if(head == NULL)
		return;
	revPrintList(head->next);
	cout << "\n" << head->data;
}

int debug(Node *head){
	cout << "\n--DEBUG: Printing list";
	Node *thisNode = head;
	while(thisNode){
		cout << "\n" << thisNode->data;
		thisNode = thisNode->next;
	}
	cout << "\n--DEBUG: List Printed\n";
}
